package demo;

/**
 *   搜索旋转排序数组
 */
class Solution22 {
	public int search(int[] nums, int target) {
		int left = 0;
		int right = nums.length - 1;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			if (nums[mid] == target) {
				return mid;
			}
			// 右边有序
			if (nums[mid] < nums[right]) {
				if (target > nums[mid] && target <= nums[right]) {
					// 目标值在右半部分
					left = mid + 1;
				} else {
					right = mid - 1;
				}
			} else if (nums[mid] >= nums[left]){
				// 左边有序
				if (nums[mid] > target && nums[left] <= target) {
					right = mid - 1;
				} else {
					left = mid + 1;
				}
			}
		}

		return -1;
	}
}

